In complied code simulation, the circuit to be simulated is converted (compiled) into an executable so that running this executable produces the same output response as the circuit without having to fabricate the circuit itself. This approach results in very fast delay-independent functional simulation (pure Boolean equation evaluation). In (Binary Decision Diagram) BDD-based compiled code simulation, the simulation executable for the circuit is derived from a BDD-based characteristic function representation of the circuit rather than from the conventional approach (called levelized compiled code simulation) of a straightforward translation of Boolean operations in the original circuit to machine instructions. Deriving the executable in this manner has been shown to result in significant speed up over the conventional approach. The speed up of delay-independent (i.e. purely functional) cycle-based logic simulation of synchronous digital circuits using BDD-based characteristic functions has been proposed in a recent article by P. Ashar and S. Malik entitled "Fast Functional Simulation Using Branching Programs" in the Proceedings of the International Conference on Computer-Aided Design, pages 408-412, November 1995 and in an article by P. McGeer, et al. entitled "Fast Discrete Function Evaluation Using Decision Diagrams" in the Proceedings of the International Conference on Computer-Aided Design, pages 402-407, November 1995. These prior art methods require that the BDD representation first be generated in C-code and then compiling the C-code to obtain assembly code.
The efficient representation and manipulation of Boolean functions is important in many applications. In particular, many problems in computer-aided design for digital circuits (CAD) can be expressed as a sequence of operations performed over a set of Boolean functions. Typical CAD applications include combinational logic verification, sequential-machine equivalence, logic optimization of combinatorial circuits, text sorting generation, timing verification in the presence of false paths, and symbolic simulation.
A binary decision diagram (BDD) is a directed acyclic graph (DAG). The graph has two sink nodes labeled 0 or 1 representing the Boolean functions 0 and 1. Each non-sink node is labeled with a Boolean variable v and has two out-edges labeled 1 (or then) and 0 (or else). Each non-sink node represents the Boolean function corresponding to its 1 edge if v=1, or the Boolean function corresponding to its 0 edge if v=0. Methods for generating BDD representations of circuits and were known in the art. One such method is described in U.S. patent application Ser. No. 08/331,075 by Ashar and Cheong, entitled "Breadth-First Manipulation Binary Decision Diagram" and assigned to the same assignee as the present invention and incorporated herein by reference.
There are two fundamental methods of generating assembly code for two-valued simulation using BDD-based characteristic functions where the BDD-based characteristic function is an executable.
One method will be referred to as the "data-centric" approach. In this approach, the BDD is stored as data in memory and a simple for loop traverses the BDD data to determine the output value. The obvious way of storing the BDD is as the 2-dimensional array. Each row corresponds to a BDD node, and each element of the array contains the address of a child node. Depending on the value of the input variable, the address of the next BDD node is determined as the content of the current address or the content of the current address incremented by one. A feature of this approach is that only 8 bytes (two 32 bit words) of storage is required per BDD node. This is the approach used in McGeer, et al. supra.
Another method of implementing the executable is to translate the BDD-based characteristic function directly into an if-then-else program. This approach will be referred to as the "instruction-centric" approach. The present invention is based on this latter approach. Using cc and gcc to compile the C-code generated from large BDDs can take an inordinately long time, especially when optimization options are used. To avoid this problem, it is necessary to generate optimized assembly code directly from the BDDs. That is a primary object of the invention.